package org.zxp.algorithm.sort;

import org.junit.Test;
import org.zxp.algorithm.sort.utils.Tools;

/**
 * @program: algorithm
 * @description: 插入排序实现
 * 每次排序还是拿一个固定的值比（和已经排好的比，插到合适的位置），其他大的要移位
 * @author: X-Pacific zhang
 * @create: 2019-04-08 11:18
 **/
public class CharuSort {
    @Test
    public void testMname() throws Exception {
        int[] oraArray = {5,2,7,4,8,7};
        long time1 = System.currentTimeMillis();
        oraArray = Tools.gen(1000000);
        long time2 = System.currentTimeMillis();
        int[] resultArray = insertSort(oraArray);
        long time3 = System.currentTimeMillis();
        Tools.printResult(resultArray, time1, time2, time3,"插入");
    }



    public int[] insertSort(int[] orgArray) throws Exception {
        for (int i = 1; i < orgArray.length; i++) {
            //            //    5 52748
            //            //    2 25748
            //            //    7 25748
            //            //    4 25478 24578 问题点出在这里不能把4 7交换，否则，就是7和5比不是4和5比了，就出现了只挪动一次，所以这里还得记录4，移动7，如下
            //    4 25778 25578  这个4最后落到它该去的位置 体现了插入两个字 -》24578
            int j = i;
            int current = orgArray[i];
            while(j > 0 && current < orgArray[j-1]){
                orgArray[j] = orgArray[j-1];
                j--;
            }
            orgArray[j] = current;//插入的动作在这
        }
        return orgArray;
    }

    public void print(String prt,int[] orgArray){
        System.out.print(prt);
        for (int ii : orgArray) {
            System.out.print(ii);
        }
        System.out.println();
    }
}
